//Given an integer array nums, return true if there exists a triple of indices (
//i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices
// exists, return false. 
//
// 
// Example 1: 
//
// 
//Input: nums = [1,2,3,4,5]
//Output: true
//Explanation: Any triplet where i < j < k is valid.
// 
//
// Example 2: 
//
// 
//Input: nums = [5,4,3,2,1]
//Output: false
//Explanation: No triplet exists.
// 
//
// Example 3: 
//
// 
//Input: nums = [2,1,5,0,4,6]
//Output: true
//Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 
//4 < nums[5] == 6.
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5 * 105 
// -231 <= nums[i] <= 231 - 1 
// 
//
// 
//Follow up: Could you implement a solution that runs in O(n) time complexity an
//d O(1) space complexity? Related Topics 贪心 数组 
// 👍 530 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Increasing Triplet Subsequence
public class P334IncreasingTripletSubsequence {
    public static void main(String[] args) {
        Solution solution = new P334IncreasingTripletSubsequence().new Solution();
//        Assert.assertEquals(solution.increasingTriplet(new int[]{5, 4, 3, 2, 1}), true);
        Assert.assertEquals(solution.increasingTriplet(new int[]{1, 2, 3, 2, 1}), true);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean increasingTriplet(int[] nums) {
            int n = nums.length;
            if (n < 3) {
                return false;
            }
            int first = nums[0], second = Integer.MAX_VALUE;
            for (int i = 1; i < n; i++) {
                int num = nums[i];
                if (num > second) {
                    return true;
                } else if (num > first) {
                    second = num;
                } else {
                    first = num;
                }
            }
            return false;
        }


        public boolean increasingTriplet1(int[] nums) {
            int n = nums.length;
            if (n < 3) {
                return false;
            }
            int[] leftMin = new int[n];
            leftMin[0] = nums[0];
            for (int i = 1; i < n; i++) {
                leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
            }
            int[] rightMax = new int[n];
            rightMax[n - 1] = nums[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
            }
            for (int i = 1; i < n - 1; i++) {
                if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                    return true;
                }
            }
            return false;
        }

        public boolean increasingTripletMy(int[] nums) {
            int length = nums.length;
            int[] piles = new int[length];
            int pile = 0;
            piles[pile] = nums[0];
            for (int i = 1; i < length; i++) {
                int num = nums[i];
                if (num > piles[pile]) {
                    piles[++pile] = num;
                } else if (num == piles[pile]) {
                    continue;
                } else {
                    int left = 0;
                    int right = pile;
                    while (left < right) {
                        int mid = (left + right) / 2;
                        if (piles[mid] > num) {
                            right = mid - 1;
                        } else if (piles[mid] == num) {
                            right = mid - 1;
                        } else {
                            left = mid + 1;
                        }
                    }
                    piles[left] = num;
                }
                if (pile >= 2) {
                    return true;
                }

            }
            return false;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}